﻿#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
//AVL树总览 ：四种旋转(LL RR LR RL)+插入+删除
// ——————————————————————
//详细思路：
// 从何处开始旋转？从最小平衡树开始旋转（下->上）
// 四种旋转：旋转+更新节点高度（取左右h最大值）
// 插入：递归插入+判断失衡
// 删除：找删除点、删除、更新高度
//————————————————————————————
//开始***************************************************
///AVL结构体节点
typedef struct AVLNode
{
	int data;
	struct AVLNode* left;
	struct AVLNode* right;
	int h;///节点高度
}AVLNode,*AVLtree;
///初始化AVL树
AVLtree init_AVL(int k)
{
	AVLNode* ro = (AVLNode*)malloc(sizeof(AVLNode));
	if (ro == NULL)
	{
		return NULL;
	}
	//初始化 指针+节点数据
	ro->data = k;
	ro->left = ro->right = NULL;
	ro->h = 1;
	return ro;
}
//返回高度（避免 空NULL 与h比较 出现bug）
int geth(AVLtree k)
{
	if (k == NULL)
	{
		return 0;
	}
	else
	{
		return k->h;
	}
}
//取极大值函数（求高度）
int Max(int a, int b)
{
	return a > b ? a : b;
}
//四种旋转
//LL 右旋（LL表示左失衡 失衡点在左）
AVLtree LL_rotation(AVLtree x)
{
	AVLNode* y = x->left;
	x->left = y->right ;
	y->right = x;

	x->h = Max(geth(x->left), geth(x->right ))+1;
	y->h = Max(geth(y->left), geth(y->right ))+1;
	return y;
}
//RR 左旋
AVLtree RR_rotation(AVLtree x)
{
	AVLNode* y = x->right ;
	x->right  = y->left ;
	y->left  = x;

	x->h = Max(geth(x->left), geth(x->right ))+1;
	y->h = Max(geth(y->left), geth(y->right ))+1;
	return y;
}
//LR 右左旋（表示左失衡 失衡点在右）
//操作：LR失衡->LL失衡->平衡(失衡点x左孩子y 进行左旋，变为LL失衡)
AVLtree LR_rotation(AVLtree x)
{
	x->left = RR_rotation(x->left);
	x= LL_rotation(x);
	return x;
}
//RL 左右旋
AVLtree RL_rotation(AVLtree x)
{
	x->right  = LL_rotation(x->right );
	x = RR_rotation(x);
	return x;
}
//AVL树插入
//ro为失衡根节点，k为待插入的元素
AVLtree insert_AVL(AVLtree ro , int k)
{
	if (ro == NULL)//递归出口
	{

		AVLNode* s = (AVLNode*)malloc(sizeof(AVLNode));//ro->s
		s->data = k;
		s->left = s->right = NULL;
		s->h = 1;
		return s;
	}
	//左插入
	else if (k < ro->data)
	{
		ro->left = insert_AVL(ro->left, k);
		//判断失衡
		if (geth(ro->left) - geth(ro->right) > 1)
		{//LL LR 
			if (k < ro->left->data)
			{//LL
				ro = LL_rotation(ro);
			}
			else
			{//LR
				ro = LR_rotation(ro);
			}
		}
	}
	//右插入
	else if (k > ro->data)
	{
		ro->right  = insert_AVL(ro->right , k);
		//判断失衡
		if (geth(ro->right ) - geth(ro->left ) > 1)
		{//RR RL
			if (k > ro->right ->data)
			{//RR
				ro = RR_rotation(ro);
			}
			else
			{//RL
				ro = RL_rotation(ro);
			}
		}
	}
	ro->h = Max(geth(ro->left), geth(ro->right ))+1;
	return ro;
}
//找根节点左子树的最右子树（找根节点的左子树的最大值）
AVLNode* find(AVLNode* ro)//AVLNode*
{
	while (ro->right != NULL)
	{
		ro = ro->right;
	}
	return ro;
}
//AVL树的删除
//ro为失衡根节点，k为待删除元素
AVLtree de_AVL(AVLtree ro, int k)
{
	//递归出口
	if (ro == NULL)
	{
		return NULL;
	}
	//1.寻k之位：k在根之左
	if (k < ro->data)
	{
		ro->left = de_AVL(ro->left, k);
		//找到了k：判断是否失衡
		if (geth(ro->right) - geth(ro->left) > 1)
		{//RR RL
			AVLNode* s = ro->right;
			if (geth(s->right )>= geth(s->left ))
			{//RR
				ro = RR_rotation(ro);
			}
			else
			{//RL
				ro = RL_rotation(ro);
			}
		}
		
	}
	//1.寻k之位：k在根之右
	else if (k > ro->data)
	{
		ro->right = de_AVL(ro->right, k);
		//找到了k：判断是否失衡
		if (geth(ro->left) - geth(ro->right) > 1)
		{//LL LR 
			AVLNode* s = ro->left ;
			if (geth(s->left ) >= geth(s->right ))
			{//LL
				ro = LL_rotation(ro);
			}
			else
			{//LR
				ro = LR_rotation(ro);
			}
		}
	}
	//2.开始删除
	else
	{
		//删除点右2个以上子节点
		if (ro->left != NULL && ro->right != NULL)
		{
			AVLNode* s = find(ro->left);
			ro->data = s->data;
			ro->left = de_AVL(ro->left, s->data);//调用递归？
			//判断是否失衡
			if (geth(ro->right) - geth(ro->left) > 1)
			{//RR RL
				AVLNode* s = ro->right;
				if (geth(s->right) >= geth(s->left))
				{//RR
					ro = RR_rotation(ro);
				}
				else
				{//RL
					ro = RL_rotation(ro);
				}
			}
		}
		//删除点右1/0个子节点
		else
		{
			//1
			AVLNode* s = NULL;
			if (ro->left != NULL)
			{
				s = ro->left;
			}
			//0
			else
			{
				s = ro->right;
			}
			free(ro);
			ro = NULL;
			return s;
		}
	}
	ro->h = Max(geth(ro->left), geth(ro->right ))+1;
	return ro;
}
//中序遍历
void inOrder(AVLtree ro)
{
	//递归出口
	if (ro == NULL)
	{
		return;
	}
	//递归条件
	if (ro->left != NULL)
	{
		inOrder(ro->left);
	}
	printf("%d %d\n", ro->data, ro->h);
	if (ro->right  != NULL)
	{
		inOrder(ro->right );
	}
}
int main()
{
	//录入数据（点的数据）
	int n;
	int a[1002];
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)
	{
		scanf("%d", &a[i]);//将点的数据存到数组里面
	}
	//初始化AVL树（建根）
	AVLtree root = init_AVL(a[1]);
	if (root == NULL)
	{
		printf("建树失败");
		return 0;
	}
	//AVL树的插入（建立AVL树）
	for (int i = 2; i <= n; i++)//从根节点之后插入
	{
		root = insert_AVL(root,a[i]);
	}
		//中序遍历
	printf("删除前：\n");
	inOrder(root);

	printf("\n删除后：\n");
	//AVL树的删除
		//中序遍历
	de_AVL(root, 2);
	inOrder(root);
	return 0;
}
/*测试一：
5
1 2 3 4 5

删除前：
1 1
2 3
3 1
4 2
5 1
删除后：
1 2
3 1
4 3
5 1

*/
/*测试二：
5
5 1 2 45 13

删除前：
1 1
2 3
5 2 
13 1
45 1
删除后：
1 2
5 3
13 1
45 1
*/
//疑问：
/*为什么返回类型是int？
int geth(AVLtree k)
{
	if (k == NULL)
	{
		return 0;
	}
	return k->h;
}
*/